package _18_剑指OfferII;

import _18_剑指OfferII.datastrcute.ListNode;

public class _027_剑指OfferII回文链表 {

    private ListNode pointListNode;

    // 递归判断
    public boolean isPalindrome(ListNode head) {
        pointListNode = head;
        return recursionCheck(head);
    }

    // 递归判断
    private boolean recursionCheck(ListNode head) {
        if (head.next == null) {
            return pointListNode.val == head.val;
        }
        if (!recursionCheck(head.next)) return false;
        pointListNode = pointListNode.next;
        return head.val == pointListNode.val;
    }

    // O(1) 空间复杂度
    public boolean isPalindrome1(ListNode head) {
        ListNode midNode = midNode(head);

        ListNode newNode = reverseListNode(midNode);

        return isSameListNode(head, newNode);
    }

    private ListNode midNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    private ListNode reverseListNode(ListNode listNode) {
        ListNode prev = null;
        while (listNode != null) {
            ListNode temp = listNode.next;
            listNode.next = prev;
            prev = listNode;
            listNode = temp;
        }
        return prev;
    }

    private boolean isSameListNode(ListNode listNode1, ListNode listNode2) {
        while (listNode2 != null) {
            if (listNode1.val != listNode2.val) return false;
            listNode1 = listNode1.next;
            listNode2 = listNode2.next;
        }
        return true;
    }


}
